package excercise.dynamic;

import java.util.Arrays;

/**
 * 约翰的干草库存已经告罄，他打算为奶牛们采购
 * H
 * (
 * 1
 * ≤
 * H
 * ≤
 * 50000
 * )
 * H(1≤H≤50000) 磅干草。
 * <p>
 * 他知道
 * N
 * (
 * 1
 * ≤
 * N
 * ≤
 * 100
 * )
 * N(1≤N≤100) 个干草公司，现在用
 * 1
 * 1 到
 * N
 * N 给它们编号。第
 * i
 * i 公司卖的干草包重量为
 * P
 * i
 * (
 * 1
 * ≤
 * P
 * i
 * ≤
 * 5
 * ,
 * 000
 * )
 * P
 * i
 * ​
 * (1≤P
 * i
 * ​
 * ≤5,000) 磅，需要的开销为
 * C
 * i
 * (
 * 1
 * ≤
 * C
 * i
 * ≤
 * 5
 * ,
 * 000
 * )
 * C
 * i
 * ​
 * (1≤C
 * i
 * ​
 * ≤5,000) 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。
 * <p>
 * 帮助约翰找到最小的开销来满足需要，即采购到至少
 * H
 * H 磅干草。
 */
public class LuoGu_P2918 {
    public int solution(int h, int[] ci, int[] vi) {
        int maxV = 0;
        for (int v : vi) {
            if (v > maxV) {
                maxV = v;
            }
        }
        return f(h, h + maxV, ci, vi);
    }

    public int f(int h, int t, int[] ci, int[] vi) {
        int m = ci.length;
        int[][] dp = new int[m + 1][t + 1];
        Arrays.fill(dp[0], 1, t + 1, Integer.MAX_VALUE);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= t; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - vi[i - 1] >= 0 && dp[i][j - vi[i - 1]] != Integer.MAX_VALUE) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - vi[i - 1]] + ci[i - 1]);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = h; i <= t; i++) {
            if (dp[m][i] < ans) {
                ans = dp[m][i];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int h = 15;
        int[] vi = {3, 5};
        int[] ci = {2, 3};

        int r = new LuoGu_P2918().solution(h, ci, vi);
        System.out.println("r = " + r);
    }

}
